package 动态数组.线性表;

import java.util.Comparator;
import java.util.Iterator;

/**
 * 手写一个线性表ArrayList集合
 * @param <E> 操作的参数
 */
public class ArrayList<E> implements List<E>{
    //默认的存储容量
    private static final int DEFAULT_CAPACITY = 10;
    //存储的数据集
    private E[] data;
    //数组中的有效元素的最后一个下标
    private int size;

    //创建默认的线性表
    public ArrayList(){
        this(DEFAULT_CAPACITY);
    }

    //创建一个指定容量的线性表
    public ArrayList(int capacity){
        if (capacity < 0){
            throw new IllegalArgumentException("initial capacity must be larger than 0");
        }
        size = 0;
        data = (E[]) new Object[capacity];
    }

    //创建指定元素的线性表
    public ArrayList(E[] arr){
        if(arr == null){
            throw new IllegalArgumentException("initial Array can not be null");
        }
        //遍历传入的数组为内部数组赋值
        data = (E[]) new Object[arr.length];
        for (E e : arr) {
            add(e);
        }
        //有效元素的个数要重置
        size = arr.length;
    }

    @Override
    public void add(E element) {
        add(size,element);
    }

    @Override
    public void add(int index, E element) {
        //判断小标是否越界
        if(index < 0 || index > size){
            throw new  IllegalArgumentException("add index out of range!");
        }
        //扩容问题
        if (size == data.length){
            resize(data.length * 2);
        }
        //移动添加角标后面的元素
        for (int i = size - 1; i >= index; i--){
            data[i + 1] = data[i];
        }
        //添加元素
        data[index] = element;
        //添加size加1
        size++;
    }

    //动态的扩缩容
    private void resize(int newLength) {
        E[] newData = (E[]) new Object[newLength];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        //更换本类数组的地址为新的数组（偷梁换柱）
        data = newData;
    }

    @Override
    public void remove(E element) {
        //删除指定的元素的时候，先获取要删除元素的下标，根据下标来删除，指定的元素
        int index = indexOf(element);
        if (index != -1){
            remove(index);
        }
    }

    @Override
    public E remove(int index) {
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("remove index out of the range!");
        }
        //移除元素，先获取当前位置的元素，后移该元素后面的元素即可
        E ret = data[index];
        for (int i = index + 1;i < size; i++){
            data[i - 1] = data[i];
        }
        //size减1
        size--;
        //考虑缩容问题，当前存储的元素的位数容量的1/4，并且默认的数组容量大于默认的容量时才缩容
        if(size == data.length / 4 && data.length > DEFAULT_CAPACITY){
            resize(data.length / 2);
        }
        return ret;
    }

    @Override
    public E get(int index) {
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("get index out of the range!");
        }
        return data[index];
    }

    @Override
    public E set(int index, E element) {
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("set index out of the range!");
        }
        E ret = data[index];
        data[index] = element;
        return ret;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            //不使用==,==判断的是地址
            if (element.equals(data[i])){
                return i;
            }
        }
        return -1;
    }

    @Override
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
    }

    @Override
    public void sort(Comparator<E> c) {
        if (c == null){
            throw  new IllegalArgumentException("comparator can not be null！");
        }
        //插入排序，进行排序
        for (int i = 1 ;i < size; i++){
            E e = data[i];
            int j = 0;
            for (j = i; j > 0 && c.compare(data[j-1],e ) > 0; j--){
                data[j] = data[j - 1];
            }
            data[j]= e;
        }
    }

    public int getCapacity(){
        return data.length;
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        if (fromIndex < 0 || toIndex >= size){
            throw new IllegalArgumentException("fromIndex or toIndex out of the range!");
        }
        if (fromIndex > toIndex){
            throw new IllegalArgumentException("formIndex must be <= toIndex!");
        }
        ArrayList list = new ArrayList();
        for (int i = fromIndex; i < toIndex; i++){
            list.add(get(i));
        }
        return list;
    }

    @Override
    public boolean equals(Object obj) {
        //判断是否为空
        if (obj == null){
            return false;
        }
        if (obj == this){
            return true;
        }
        //判断类型是否相等
        if (getClass() != obj.getClass()){
            return false;
        }
        //类型相同就转换类型
        ArrayList other = (ArrayList) obj;
        for (int i= 0 ;i < size; i++){
            if (!get(i).equals(other.get(i))){
                return false;
            }
        }
        return true;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("%d/%d ", size, getCapacity()));
        sb.append('[');
        if (isEmpty()){
            sb.append(']');
        }else {
            for (int i = 0; i < size; i++) {
                sb.append(get(i));
                if (i == size -1){
                    sb.append(']');
                }else {
                    sb.append(',');
                }
            }
        }
        return sb.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayListIterator();
    }

    public void swap(int i, int j) {
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    class ArrayListIterator implements Iterator<E>{

        private int cur = 0;

        @Override
        public boolean hasNext() {
            return cur < size;
        }

        @Override
        public E next() {
            return data[cur++];
        }
    }
}
